package _08;
/*
问题描述
　　小明有一块空地，他将这块空地划分为 n 行 m 列的小块，每行和每列的长度都为 1。
　　小明选了其中的一些小块空地，种上了草，其他小块仍然保持是空地。
　　这些草长得很快，每个月，草都会向外长出一些，如果一个小块种了草，
    则它将向自己的上、下、左、右四小块空地扩展，这四小块空地都将变为有草的小块。
　　请告诉小明，k 个月后空地上哪些地方有草。
输入格式
　　输入的第一行包含两个整数 n, m。
　　接下来 n 行，每行包含 m 个字母，表示初始的空地状态，字母之间没有空格。如果为小数点，表示为空地，如果字母为 g，表示种了草。
　　接下来包含一个整数 k。
输出格式
　　输出 n 行，每行包含 m 个字母，表示 k 个月后空地的状态。如果为小数点，表示为空地，如果字母为 g，表示长了草。
样例输入
4 5
.g...
.....
..g..
.....
2
样例输出
gggg.
gggg.
ggggg
.ggg.
评测用例规模与约定
　　对于 30% 的评测用例，2 <= n, m <= 20。
　　对于 70% 的评测用例，2 <= n, m <= 100。
　　对于所有评测用例，2 <= n, m <= 1000，1 <= k <= 1000。
*/
//n 行 m 列的小块，每行和每列的长度都为 1。
//向自己的上、下、左、右四小块空地扩展
//k 个月后空地上哪些地方有草。

import java.util.LinkedList;
import java.util.Queue;
import java.util.Scanner;
//思路：
//采用广度优先搜索的想法，设置一个队列，
// 第0月开始长草的先入队，然后将四周的下一个月长草的入队后出队，直到月份为K
/*public class _08_2 {
    public static void main(String[] args) {
        Scanner scn = new Scanner(System.in);
        int n = scn.nextInt(), m = scn.nextInt();
        char[][] a = new char[n][m];
        String line;
        Queue<Node> queue = new LinkedList();
        for (int i = 0; i < n; i++) {
            line = scn.next();
            for (int j = 0; j < m; j++) {
                a[i][j] = line.charAt(j);
                if (a[i][j] == 'g') {
                    queue.offer(new Node(i, j, 0));//0月入队
                }
            }
        }
        int k = scn.nextInt();
        while (!queue.isEmpty()) {
            Node q = queue.poll();
            if (q.cnt == k + 1)
                break;
            a[q.x][q.y] = 'g';
            //下
            if (q.x + 1 < n && a[q.x + 1][q.y] != 'g') {
                queue.offer(new Node(q.x + 1, q.y, q.cnt + 1));
            }
            //上
            if (0 <= q.x - 1 && a[q.x - 1][q.y] != 'g') {
                queue.offer(new Node(q.x - 1, q.y, q.cnt + 1));
            }
            //右
            if (q.y + 1 < m && a[q.x][q.y + 1] != 'g') {
                queue.offer(new Node(q.x, q.y + 1, q.cnt + 1));
            }
            //左
            if (0 <= q.y - 1 && a[q.x][q.y - 1] != 'g') {
                queue.offer(new Node(q.x, q.y - 1, q.cnt + 1));
            }
        }
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                System.out.print(a[i][j]);
            }
            System.out.println();
        }
    }

}*/

